Menjelang 432, Huns bersatu di bawah Rua. Pada tahun 434, Rua meninggal dunia, meninggalkan anak saudaranya Attila dan Bleda, anak kepada saudara lelakinya Mundzuk, bagi mengawal persekutuan suku-kaum Hun. Pada ketika penabalan mereka, kaum Hun sedang berunding dengan wakil Theodosius II mengenai pemulangan beberapa kaum yang berpaling tadah yang mencari perlindungan di Empayar Byzantine.

Pada tahun berikutnya, Attila dan Bleda bertemu dengan wakil maharaja di Margus (masa kini Požarevac) dan kesemua mereka duduk di belakang kuda menurut adat kaum Hun, berunding perjanjian yang berjaya: orang Rom bersetuju untuk memulangkan kaum pelarian (yang merupakan bantuan diperlukan bagi menentang Vandals), tetapi juga mengandakan hantaran 350 paun Rom (sekitar. 114.5 kg) emas dahulu, membuka pasar mereka kepada pedagang Hun, dan membayar tebusan lapan siling solidus bagi setiap orang tahanan Rom yang ada di tangan puak Hun. Puak Hun, berpuas hati dengan perjanjian tersebut, beredar dari empayar dan bergerak ke tengah benua, kebarangkalinya untuk mengukuhkan dan memperkuat empayar mereka. Theodosius menggunakan peluang ini bagi mengukuhkan dinding Constantinople, membina dinding laut bandar Constantinople yang pertama, dan membina pertahanan sempadan sepanjang Danube.

Berpuas hati buat seketika, raja-raja Hun berundur ke pedalaman empayar mereka. Menurut Jordanes (menurut Priscus), tidak lama semasa keamanan selepas pengunduran Hun dari Byzantium (kebarangkaliannya sekitar 445), Bleda meninggal dunia, dan Atilla menduduki takhta seorang diri. Terdapat perdebatan di kalangan pakar sejarah mengenai sama ada Attila membunuh saudaranya, atau sama ada Bleda meninggal disebabkan lantaran lain. Apa-apa pun, Attila sekarang merupakan ketua yang tidak dipertikaikan bagi puak Hun, dan dia kembali memberi perhatiannya ke arah bahagian timur empayarnya.

• Priscus dari Panium: serpihan daripada Kedutaan kepada Attila